#define  _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

namespace jc
{
	template<class T>
	struct TreeNode
	{
		TreeNode* _left;
		TreeNode* _right;
		T _key;

		TreeNode(const T& key)
			:_left(nullptr)
			,_right(nullptr)
			,_key(key)
		{}
	};

	template<class T>
	class BSTree
	{
		typedef TreeNode<T> Node;
	public:
		
		bool Insert(const T& key)
		{
			if (_root == nullptr){
				_root = new Node(key);
				return true;
			}

			Node* Parent = _root;
			Node* Child = _root;
			while (Child)
			{
				if (key < Child->_key){
					Parent = Child;
					Child = Child->_left;
				}
				else if (key > Child->_key){
					Parent = Child;
					Child = Child->_right;
				}
				else{
					return false;
				}
			}

			Child = new Node(key);

			if (Child->_key < Parent->_key)
			{
				Parent->_left = Child;
			}
			else
			{
				Parent->_right = Child;
			}
			return true;
		}

		bool FindTree(const T& key)
		{
			Node* Child = _root;
			while (Child)
			{
				if (key < Child->_key)
				{
					Child = Child->_left;
				}
				else if (key > Child->_key)
				{
					Child = Child->_right;
				}
				else
				{
					return true;
				}
			}
			return false;
		}

		bool Erase(const T& key)
		{
			Node* Parent=_root;
			Node* cur = _root;
			while (cur)
			{
				if (key < cur->_key){
					Parent = cur;
					cur = cur->_left;
				}
				else if (key > cur->_key){
					Parent = cur;
					cur = cur->_right;
				}
				else{
					if (cur->_left == nullptr) {
						if (cur == _root) {
							Parent = cur->_right;
							delete cur;
						}
						else
						{
							if (cur == Parent->_right) {
								Parent->_right = cur->_right;
							}
							else {
								Parent->_left = cur->_right;
							}
						}
					}
					else if (cur->_right == nullptr) {
						if (cur == _root) {
							Parent = cur->_right;
							delete cur;
						}
						else
						{
							if (cur == Parent->_right) {
								Parent->_right = cur->_left;
							}
							else {
								Parent->_left = cur->_left;
							}
						}
					}
					else {
						Node* MinChild = cur->_right;
						Node* MinParent = cur;
						while (MinChild->_left)
						{
							MinParent = MinChild;
							MinChild = MinChild->_left;
						}
						cur->_key = MinChild->_key;
						if (MinChild == MinParent->_left)
						{
							MinParent->_left = MinChild->_right;
							delete MinChild;
						}
						else
						{
							MinParent->_right = MinChild->_right;
							delete MinChild;
						}
					}
					return true;
				}
			}
			return false;
		}

		void MidOrder()
		{
			MidOrderTest(_root);
			cout << endl;
		}
	
	private:
		void MidOrderTest(Node* _root)
		{
			if (_root == nullptr)
			{
				return;
			}
			MidOrderTest(_root->_left);
			cout << _root->_key << " ";
			MidOrderTest(_root->_right);
		}

		Node* _root = nullptr;
	};
}

int main()
{
	int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
	jc::BSTree<int> BST;
	for (auto i : arr)
	{
		BST.Insert(i);
	}
	BST.MidOrder();
	BST.Erase(4);
	BST.MidOrder();


	return 0;
}//